Nous sommes toutes distinctes - Olympiades 2024 Exercice 2

Dans cet exercice, le symbole  \(n\) désigne un entier naturel, avec  \(n \ge 1\) ; tous les ensembles considérés sont non vides, finis et constitués de nombres réels distincts ; de plus, on conviendra d’écrire tout ensemble fini  \(A= \{a_1, \ldots, a_n\}\) à  \(n\) éléments réels distincts en ordonnant toujours \(a_1, a_2, \cdots, a_n\)  si bien que \(a_1< a_2< \cdots. Étant donné un tel ensemble, on note  \(S(A)\) la somme de ses éléments, soit :

\(\hspace{5 cm}S(A)=a_1+\cdots+a_n\)

\(\) En particulier, lorsque  \(n=1\) et donc  \(A=\{a_1\}\)  est un singleton,  \(S(A) = a_1\) .

On dit que l’ensemble  \(A\) est à sommes toutes distinctes (en abrégé que  \(A\) est STD) quand, pour toutes parties non vides distinctes  \(Y\) et  \(Z\) de \(A\) , \(S(Y) \neq S(Z)\) . Cela revient à demander aux  \(2^n-1\) sommes que l’on peut former avec des éléments de  \(A\)  d’être toutes distinctes.

Par exemple,  \(A=\{1,2,5\}\) est STD parce que les nombres \(1,2,5,1+2=3, 2+5=7, 1+5=6, 1+2+5=8\)   sont tous distincts. En revanche,  \(A=\{2,4,6,7\}\) n’est pas STD parce qu’en prenant  \(Y=\{2,4,7\}\) et \(Z=\{6,7\}\) , on a  \(S(Y)= 2+4+7=13\)   \(=S(Z)\) , bien que \(Y \neq Z\) .

Partie 1 - Exemples et contre-exemples simples

1. Expliquer pourquoi le nombre de sommes à envisager pour étudier le caractère STD de  \(A\) vaut \(2^n-1\) .

2. Montrer que l’ensemble  \(\{1,3,5\}\) est STD mais que l’ensemble \(\{4,6,7,9\}\)  ne l’est pas.

3. Quel(s) ensemble(s)  \(A\) contenant  \(0\) est (sont) STD  ?

4. Soit  \(A\) et  \(B\) deux ensembles non vides et finis de réels distincts, avec  \(A\subset B\) (c’est-à-dire que  \(A\) est un sous-ensemble de \(B\) ).
    a. Si  \(B\) est STD, justifier que  \(A\) l’est aussi.
    b. L’ensemble  \(B\) peut-il être STD si  \(A\) ne l’est pas ? 

5. Soit  \(A\) un ensemble non vide et fini de réels distincts. On suppose que  \(A\) n’est constitué que de nombres entiers et qu’il est STD. Justifier que  \(\displaystyle A \cup \left\{\frac{1}{2}\right\}\) puis que  \(\displaystyle A\cup \left\{ \frac{1}{2} , \sqrt2\right\}\) sont aussi STD.

Partie 2 - Construction d’une suite

On considère la suite  \((u_n)\) définie par  \(u_1=1\) et par la relation de récurrence, valable pour tout \(n \ge1\) ,

\(u_{(n+1)}=u_1+ \cdots+u_n+1\)

6. Vérifier que \(u_2=2\)  et \(u_3=4\) . Calculer \(u_5\) .

7. Rédiger sur votre copie un programme en langage Python qui renverrait  \(u_{100}\) (qu’on ne calculera pas).

8. Étudier le sens de variation de la suite \((u_n)\) .

9. Montrer que, pour tout \(n \ge1\) , l’ensemble  \(\{u_1, \cdots, u_n\}\) est STD.

10. Montrer que  \((u_n)\) est en fait une suite géométrique que l’on déterminera.

Partie 3 - Suites STD

Une suite  \((u_n)\) est dite STD lorsqu’elle est strictement croissante, qu’elle est composée d’entiers strictement positifs et que, pour tout \(n \ge1\) , l’ensemble  \(\{u_1, \cdots, u_n\}\) est STD.

Par exemple, la suite étudiée dans la partie 2 est une suite STD.

11. Soit (𝑢𝑛) une suite STD quelconque.
    a. Montrer que pour tout  \(n \ge1\) :  \(u_1+ \cdots+u_n \ge2^n-1\) .

     b. En déduire que pour tout  \(n \ge2\) :  \(u_n \ge\dfrac{2^n}{n}\) .

12. Le but cette question est d’affiner la minoration obtenue à la question précédente. Pour ce faire, nous aurons recours aux probabilités, et nous dirons qu’une variable aléatoire  \(X\) à valeurs dans un ensemble réel fini non vide \(A= \{a_1, \cdots,a_n\}\)  à  \(n\) éléments distincts suit une loi uniforme quand toutes les valeurs qu’elle peut atteindre sont équiprobables. Ainsi,

\(P(X=a_1) = P(X=a_2)= \cdots=P(X=a_n)=\dfrac{1}n{}\) .
    a. Soit  \((u_n)\) une suite STD quelconque. Pour  \(n\ge 2\) , on considère les variables aléatoires indépendantes  \(X_1, \ldots,X_n\) qui suivent la loi uniforme sur la paire  \(\{-1,1\}\) : ainsi, pour chacun des indices \(i, P(X_i=1)=P(X_i=-1)=\dfrac{1}{2}\) . 
On pose \(X=u_1X_1+ \cdots+u_nX_n\) .
On admet que \(E(X)=u_1E(X_1)+\cdots+u_nE(X_n)\)  et que \(V(X)=u^2_1V(X_1)+\ldots+u^2_n(X_n)\) .
Après avoir justifié que  \(E(X_1)=0\) et \(V(X_1)=1\) , calculer l’espérance  \(E(X)\) et exprimer la variance  \(V(X)\) en fonction de \(u_1,u_2,\cdots, u_n\) .
    b. Montrer que  \(X\) suit une loi uniforme sur un ensemble de  \(2^n\) entiers relatifs, symétrique par rapport à \(0\) , et dont les éléments sont non nuls et de la même parité.
    c. En déduire que pour \(n\ge1\) ,  \({u_{n}}^2\ge\dfrac{1}{n2^{n-1}}(1^2+3^2+5^2+ \cdots+(2^n-1)^2)\) .
    d. Proposer une valeur de  \(n\ge2\) pour laquelle cette inégalité fournit un minorant plus grand qu’en 11.b.